/*给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
* 你可以假设数组中无重复元素。
*
* 输入: [1,3,5,6], 5
* 输出: 2
* */

package newcoder.BinarySearch_4;

public class Leetcode35 {

    public static void main(String[] args) {

        Leetcode35 obj = new Leetcode35();
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        System.out.println(obj.searchInsert(nums, target));
    }

    public int searchInsert(int[] nums, int target){

        if (target > nums[nums.length - 1]){
            return nums.length;
        }
        int pivot = 0, left = 0, right = nums.length - 1;
        while (left <= right){
            pivot = (right + left) / 2;
            if (target == nums[pivot]){
                return pivot;
            }else if (target <= nums[pivot]){
                right = pivot - 1;
            }else {
                left = pivot + 1;
            }
        }
        return left;
    }
}
